package com.leetcode;

import com.sun.xml.internal.stream.buffer.sax.DefaultWithLexicalHandler;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @Classname Leetcode146
 * @Description TODO
 * @Date 2021-08-23 21:33
 * @Created by darrren
 */

//时间复杂度：对于 put 和 get 都是 O(1)O(1)O(1)。
//
//空间复杂度：O(capacity)O(\text{capacity})O(capacity)，因为哈希表和双向链表最多存储 capacity+1\text{capacity} + 1capacity+1 个元素。
//
class LRUCache {
    /*
   *    java 双向链表
     */
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    // cache hash表缓存数据，使得get 和 set 时间复杂度是O(1)
    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        //创建 dummy head 和 tail，这样子在添加和删除时不需要考虑相邻的节点是否存在
        head = new DLinkedNode();
        tail = new DLinkedNode();


        // head 和tail初始化，不需要进行 head.pre = tail 和 tail.next=head,因为不需要用到
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
       if(cache.get(key) == null){
           return -1;
       }

       //每次访问，将访问的元素放在列表头部
       DLinkedNode node = cache.get(key);
       moveToHead(node);
       return node.value;
    }

    public void put(int key, int value) {
        if(cache.get(key) != null){
            //如果cache中有数据，需要更新 node 数据并且将 node 移动到头部
           DLinkedNode dLinkedNode = cache.get(key);
            dLinkedNode.value = value;
            moveToHead(dLinkedNode);
        }else{
            //创建新的节点并且加入到cache和双向链表中
            DLinkedNode dLinkedNode = new DLinkedNode(key,value);
            cache.put(key,dLinkedNode);
            addToHead(dLinkedNode);
            size++;

            //如果size超出，则需要从cache和双向链表中删除
            if(size > capacity){
                //通过双向链表，可以快速找到最后一个节点并且删除
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
                size--;
            }

        }

    }

    //双向链表插入操作
    private void addToHead(DLinkedNode node) {
        //记住先操作新节点
        node.prev = head;
        node.next = head.next;

        //再操作原有的节点
        //可以防止指向被覆盖
        head.next.prev = node;
        head.next = node;
    }

    //双向链表删除操作
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    //先删除，在加入到头部
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    //tail.prev找到最后一个节点,不需要遍历
    private DLinkedNode removeTail() {
        DLinkedNode dLinkedNode = tail.prev;
        removeNode(dLinkedNode);
        return dLinkedNode;
    }
}


public class Leetcode146 {
    public static void main(String[] args){
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get(1));
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        System.out.println(lRUCache.get(2));
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        System.out.println(lRUCache.get(1));
        System.out.println(lRUCache.get(3));
        System.out.println(lRUCache.get(4));

    }
}
//output
//1,-1,-1,3,4
